package 查找算法;

import java.util.Arrays;

/*
* 斐波那契查找算法
* 黄金分割
* 斐波那契数列{1,1,2,3,5,8,13,21,34,55,89......}
* 相邻两个数的比例无限接近0.618
* */
public class FibonacciSearch {
    public static int capacity = 20;
    public static int[] f = new int[capacity];
    public static void main(String[] args) {
        int[] arr = {1,8,10,98,123,1234,2134};
        int i = fibSearch(arr, 10);
        System.out.println(i);
    }

    /**
     * 斐波那契查找算法
     * 非递归实现
     * @param a 斐波那契数组
     * @param value 要查找的值
     * @return 返回查找元素的下标
     */
    public static int fibSearch(int[] a,int value){
        int low = 0;
        int high = a.length-1;
        int k = 0;// 分割数值的下标
        int mid = 0;
        int[] f = fib1();// 获取斐波那契数列
        // 获取k
        while(high > f[k] - 1){
            k++;
        }

        // 因为f[k]的值可能大于a
        int[] temp = Arrays.copyOf(a,f[k]);

        for (int i = high+1; i < temp.length; i++) {
            temp[i] = a[high];
        }

        while(low<=high){
            mid = low+f[k-1]-1;
            if(value < temp[mid]){
                high = mid - 1;
                k--;
            }else if(value > temp[mid]){
                low = mid+1;
                k-=2;
            }else{
                if(mid<= high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }

    /*
     * 因为后面mid =low + F(k-1) - 1 ,需要用到斐波那契数列,在这里先写一个斐波那契数列
     *  1.非递归
     *  2.递归
     * */
    public static int[] fib1(){
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < capacity; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }
     public static int fib2(int[] f,int i){
        if(i == 0 || i == 1){
            return 1;
        }
        return f[i] = fib2(f,i-1)+fib2(f,i-2);
     }
}
